package com.fml.dataStructure.search;

/**
 * 二分查找
 */
public class BinarySearch {


    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15}; // 必须是有序数组
        int target = 7;
        int result = binarySearch(sortedArray, target);

        if (result != -1) {
            System.out.println("元素 " + target + " 找到，索引位置: " + result);
        } else {
            System.out.println("元素未找到");
        }
    }


    /**
     * 二分查找实现
     * @param arr    有序数组（升序排列）
     * @param target 要查找的目标值
     * @return 目标值在数组中的索引，未找到返回-1
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;//防止整数溢出
            if (arr[mid] == target) {
                return mid;//找到目标
            } else if (arr[mid] < target) {//目标在右侧部分
                left = mid + 1;
            } else {//目标在左侧部分
                right = mid - 1;
            }
        }
        return -1;//没找到
    }

}
